<?php
/**
 * 默写排序、查找
 * 排序
 * 1.快速排序
 * 2.冒泡排序
 * 3.归并排序
 * 4.插入排序
 * 查找 二分查找
 */
$arr = array(10,6,3,21,21,8,1,5,12,21,10,2);
$arr = Qsort($arr);
//$arr = mergeSort($arr);
//$arr = bubble($arr);
//$arr = pushSort($arr);
//$arr = insertSort($arr);

var_dump(search($arr, 6));
var_dump($arr);

/*
 *  1快速排序 也是一种合并排序 和数组的一个数比较 生成比这个数小的数组 和 比这个数大的数组,递归比较这两个数组
 *
 */
function Qsort($arr) {
    if (2 > count($arr)) return $arr;
    $value =  array_shift($arr);
    $a = [];
    $b = [];
    $c = [$value];
    foreach ($arr as $v) {
       if ($value > $v) {
           $a[] = $v;
       } elseif($value < $v) {
           $b[] = $v;
       } else {
           $c[] = $v;
       }
    }
    $a = Qsort($a);
    $b = Qsort($b);
    $arr = array_merge($a, $c, $b);
    return $arr;
}

/**
 * 3.归并排序 二分拆分 无线拆分为单个元素 比较 合并为排序的数组
 * 已排序的数组的两个数组 排序
 */
function mergeSort($arr) {
    $count = count($arr);
    if ($count < 2) {
        return $arr;
    }
    $midIndex = ceil($count/2);
    $a = array_slice($arr,0, $midIndex);
    $b = array_slice($arr, $midIndex);
    $a = mergeSort($a);
    $b = mergeSort($b);
    return mergeSorted($a, $b);
}

function mergeSorted($a, $b) {
    $result = [];
    $i = 0;
    $j = 0;
    //排序两个数组中的小值 会有个空数组,和一个剩余数组
    while($i <count($a) && $j < count($b)) {
        if ($a[$i] < $b[$j]) {
            $result[] = $a[$i];
            $i++;
        } else {
            $result[] = $b[$j];
            $j++;
        }
    }
    while ($i <count($a)) {
        $result[] = $a[$i];
        $i++;
    }
    while ($j <count($b)) {
        $result[] = $b[$j];
        $j++;
    }
    return $result;
}


/*2.交换排序 冒泡排序
 * 下沉排序 依次比较相邻的元素 第一轮排序最后一个元素最大
 *
 */
function bubble($arr) {
    $n = count($arr);
    $i = $n-1;   //$i是每轮最大比较的下标
    for(; $i > 0; $i--) {
        for($j=0;$j < $i; $j++) {
            if ($arr[$j] > $arr[$j+1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $temp;
            }
        }
    }
    return $arr;
}

//2.交换排序 比较当前的元素和其他元素 第一轮排序后第一个元素最小,依次拿第二,三元素到最会
function pushSort($arr) {
    $n = count($arr);
    for($i=0; $i < $n; $i++) {
        for($j = $i+1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$i]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$i];
                $arr[$i] = $temp;
            }
        }
    }
    return $arr;
}

/**
 * 4. 插入排序 将元素插入到已经排序好的数组,有点像归并排序
 * 第一个元素是已经排序好的,要遍历的是后面的元素
 * 取出元素 和 已排序的元素对比 大的元素后移,取出的元素大,就不在比较,将取出的元素放在合适的位置
 */
function insertSort($arr) {
    //$i 第一次比较的元素下标
    for($i=1;$i < count($arr); $i++) {
        $value = $arr[$i];
       //已排序好的元素最大的元素下标 $i-1
        //取出元素可能要插入的位置
        $j= $i;
        while($j > 0 && $value < $arr[$j-1]){
            $arr[$j] = $arr[$j-1];  //大的元素后移
            $j--;                   //取出元素要插入的位置
        }
        $arr[$j] = $value;
    }
    return $arr;
}

/**
 * 二分查找 只返回是否存在
 */

function search($arr, $searchV) {
    $n  = count($arr);
    if ($n < 1) {
        return false;
    }
    $midIndex = intval($n/2);
    if ($searchV == $arr[$midIndex]) {
        return true;
    }
    if ($arr[$midIndex] > $searchV) {
        $arr = array_slice($arr, 0,$midIndex);

    } elseIf($arr[$midIndex] < $searchV) {
        $arr = array_slice($arr, $midIndex+1);
    }
    return search($arr, $searchV);
}